package msb.class01;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

import java.util.*;

/**
 * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
 * <p>
 * 解题思路
 * 1.全部数字异或后结果为目标两个数字的异或结果
 * 2.目标两个数字的异或结果的最后一位二进制为1的位表示目标数在该位置的值不同
 * 3.将数组按该位置的分组，将值为1的进行异或运算，得到一号数字
 * 4.将所有数字结果与一号数字异或，得到二号数字
 * <p>
 * 假设
 * 一号数字：10010101001000
 * 二号数字：10010100100000
 * <p>
 * 异或结果：xxxxxxxxxx1000
 */
public class Code09_TwoOddOtherEven {

    public static int[] getNum(int[] arr) {
        int[] result = new int[2];

        //所有数异或结果
        int eor = 0;
        for (int num : arr) {
            eor = eor ^ num;
        }

        //异或结果最后一位
        int flag = eor & (-eor);

        // a ^ flag == 1 表示数字的flag位置为1
        int eor2 = 0;
        for (int num : arr) {
            if ((num & flag) == 0) {
                eor2 = eor2 ^ num;
            }
        }

        result[0] = eor2;
        result[1] = eor2 ^ eor;
        return result;
    }

    @Test
    public void check() {
        for (int i = 0; i < 10000; i++) {
            List<int[]> ints = ArrayUtil.instantOddAndEven(2);
            int[] arr = ints.get(0);
            int[] odds = ints.get(1);
            int[] result = getNum(arr);
            Arrays.sort(odds);
            Arrays.sort(result);
            Assert.assertEquals(odds[0], result[0]);
            Assert.assertEquals(odds[1], result[1]);
        }
    }

}
